home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / dev / c / BinaryTrees.lzh / ubi_AVLtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-07-26  |  27.3 KB  |  691 lines
  1. /* ========================================================================== **
  2.  *                              ubi_AVLtree.c
  3.  *
  4.  *  Copyright (C) 1991-1997 by Christopher R. Hertel
  5.  *
  6.  *  Email: crh@ubiqx.mn.org
  7.  * -------------------------------------------------------------------------- **
  8.  *
  9.  *  This module provides an implementation of AVL height balanced binary
  10.  *  trees.  (Adelson-Velskii, Landis 1962)
  11.  *
  12.  *  This file implements the core of the height-balanced (AVL) tree management
  13.  *  routines.  The header file, ubi_AVLtree.h, contains function prototypes
  14.  *  for all "exported" functions.
  15.  *
  16.  * -------------------------------------------------------------------------- **
  17.  *
  18.  *  This library is free software; you can redistribute it and/or
  19.  *  modify it under the terms of the GNU Library General Public
  20.  *  License as published by the Free Software Foundation; either
  21.  *  version 2 of the License, or (at your option) any later version.
  22.  *
  23.  *  This library is distributed in the hope that it will be useful,
  24.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26.  *  Library General Public License for more details.
  27.  *
  28.  *  You should have received a copy of the GNU Library General Public
  29.  *  License along with this library; if not, write to the Free
  30.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31.  *
  32.  * -------------------------------------------------------------------------- **
  33.  *
  34.  * $Log: ubi_AVLtree.c,v $
  35.  * Revision 2.4  1997/07/26 04:36:20  crh
  36.  * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
  37.  * on backwards with respect to node deletion.  I did some more digging and
  38.  * discovered that I was not changing the balance values correctly in the
  39.  * single rotation functions.  Double rotation was working correctly because
  40.  * the formula for changing the balance values is the same for insertion or
  41.  * deletion.  Not so for single rotation.
  42.  *
  43.  * I have tested the fix by loading the tree with over 44 thousand names,
  44.  * deleting 2,629 of them (all those in which the second character is 'u')
  45.  * and then walking the tree recursively to verify that the balance factor of
  46.  * each node is correct.  Passed.
  47.  *
  48.  * Thanks Andrew!
  49.  *
  50.  * Also:
  51.  * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
  52.  * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
  53.  *   hoped they would do (see the bottom of the header file).  They work now.
  54.  *
  55.  * Revision 2.3  1997/06/03 04:41:35  crh
  56.  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
  57.  * problems.
  58.  *
  59.  * Revision 2.2  1995/10/03 22:16:01  CRH
  60.  * Ubisized!
  61.  *
  62.  * Revision 2.1  95/03/09  23:45:59  CRH
  63.  * Added the ModuleID static string and function.  These modules are now
  64.  * self-identifying.
  65.  * 
  66.  * Revision 2.0  95/03/05  14:10:51  CRH
  67.  * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
  68.  * and so includes all of the changes to that module.  In addition, a bug in
  69.  * the node deletion process has been fixed.
  70.  *
  71.  * After rewriting the Locate() function in ubi_BinTree, I decided that it was
  72.  * time to overhaul this module.  In the process, I discovered a bug related
  73.  * to node deletion.  To fix the bug, I wrote function Debalance().  A quick
  74.  * glance will show that it is very similar to the Rebalance() function.  In
  75.  * previous versions of this module, I tried to include the functionality of
  76.  * Debalance() within Rebalance(), with poor results.
  77.  *
  78.  * Revision 1.0  93/10/15  22:58:56  CRH
  79.  * With this revision, I have added a set of #define's that provide a single,
  80.  * standard API to all existing tree modules.  Until now, each of the three
  81.  * existing modules had a different function and typedef prefix, as follows:
  82.  *
  83.  *       Module        Prefix
  84.  *     ubi_BinTree     ubi_bt
  85.  *     ubi_AVLtree     ubi_avl
  86.  *     ubi_SplayTree   ubi_spt
  87.  *
  88.  * To further complicate matters, only those portions of the base module
  89.  * (ubi_BinTree) that were superceeded in the new module had the new names.
  90.  * For example, if you were using ubi_AVLtree, the AVL node structure was
  91.  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
  92.  * SplayTree, the locate function was called "ubi_sptLocate", but the next
  93.  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
  94.  *
  95.  * This was not too terrible if you were familiar with the modules and knew
  96.  * exactly which tree model you wanted to use.  If you wanted to be able to
  97.  * change modules (for speed comparisons, etc), things could get messy very
  98.  * quickly.
  99.  *
  100.  * So, I have added a set of defined names that get redefined in any of the
  101.  * descendant modules.  To use this standardized interface in your code,
  102.  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
  103.  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
  104.  * datatype names for the module that you are using.  Just remember to
  105.  * include the header for that module in your program file.  Because these
  106.  * names are handled by the preprocessor, there is no added run-time
  107.  * overhead.
  108.  *
  109.  * Note that the original names do still exist, and can be used if you wish
  110.  * to write code directly to a specific module.  This should probably only be
  111.  * done if you are planning to implement a new descendant type, such as
  112.  * red/black trees.  CRH
  113.  *
  114.  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
  115.  *
  116.  *  ========================================================================= **
  117.  */
  118.  
  119. #include "ubi_AVLtree.h"            /* Header for THIS module.             */
  120. #include <stdlib.h>                 /* Standard C definitions, etc.        */
  121.  
  122. /* ========================================================================== **
  123.  * Static data.
  124.  */
  125.  
  126. static char ModuleID[] = "ubi_AVLtree\n\
  127. \t$Revision: 2.4 $\n\
  128. \t$Date: 1997/07/26 04:36:20 $\n\
  129. \t$Author: crh $\n";
  130.  
  131. /* ========================================================================== **
  132.  * The next set of functions are the AVL balancing routines.  There are left
  133.  * and right, single and double rotations.  The rotation routines handle the
  134.  * rotations and reconnect all tree pointers that might get confused by the
  135.  * rotations.  A pointer to the new subtree root node is returned.
  136.  *
  137.  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
  138.  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
  139.  * a clever way to reduce the amount of code by combining these functions,
  140.  * but it might involve additional overhead, and it would probably be a pain
  141.  * to read, debug, etc.
  142.  * -------------------------------------------------------------------------- **
  143.  */
  144.  
  145. static ubi_avlNodePtr L1( ubi_avlNodePtr p )
  146.   /* ------------------------------------------------------------------------ **
  147.    * Single rotate left.
  148.    *
  149.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  150.    *  Output: A pointer to the new root of the same subtree (now that node
  151.    *          p has been moved).
  152.    * ------------------------------------------------------------------------ **
  153.    */
  154.   {
  155.   ubi_avlNodePtr tmp;
  156.  
  157.   tmp                = p->Link[RIGHT];
  158.   p->Link[RIGHT]     = tmp->Link[LEFT];
  159.   tmp->Link[LEFT]    = p;
  160.  
  161.   tmp->Link[PARENT]  = p->Link[PARENT];
  162.   tmp->gender        = p->gender;
  163.   if(tmp->Link[PARENT])
  164.     (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp;
  165.   p->Link[PARENT]    = tmp;
  166.   p->gender          = LEFT;
  167.   if( p->Link[RIGHT] )
  168.     {
  169.     p->Link[RIGHT]->Link[PARENT] = p;
  170.     (p->Link[RIGHT])->gender     = RIGHT;
  171.     }
  172.   p->balance -= Normalize( tmp->balance );
  173.   (tmp->balance)--;
  174.   return( tmp );
  175.   } /* L1 */
  176.  
  177. static ubi_avlNodePtr R1( ubi_avlNodePtr p )
  178.   /* ------------------------------------------------------------------------ **
  179.    * Single rotate right.
  180.    *
  181.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  182.    *  Output: A pointer to the new root of the same subtree (now that node
  183.    *          p has been moved).
  184.    * ------------------------------------------------------------------------ **
  185.    */
  186.   {
  187.   ubi_avlNodePtr tmp;
  188.  
  189.   tmp                = p->Link[LEFT];
  190.   p->Link[LEFT]      = tmp->Link[RIGHT];
  191.   tmp->Link[RIGHT]   = p;
  192.  
  193.   tmp->Link[PARENT]  = p->Link[PARENT];
  194.   tmp->gender        = p->gender;
  195.   if(tmp->Link[PARENT])
  196.     (tmp->Link[PARENT])->Link[(tmp->gender)] = tmp;
  197.   p->Link[PARENT]    = tmp;
  198.   p->gender          = RIGHT;
  199.   if(p->Link[LEFT])
  200.     {
  201.     p->Link[LEFT]->Link[PARENT]  = p;
  202.     p->Link[LEFT]->gender        = LEFT;
  203.     }
  204.   p->balance -= Normalize( tmp->balance );
  205.   (tmp->balance)++;
  206.   return( tmp );
  207.   } /* R1 */
  208.  
  209. static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
  210.   /* ------------------------------------------------------------------------ **
  211.    * Double rotate left.
  212.    *
  213.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  214.    *  Output: A pointer to the new root of the same subtree (now that node
  215.    *          p has been moved).
  216.    * ------------------------------------------------------------------------ **
  217.    */
  218.   {
  219.   ubi_avlNodePtr tmp, newroot;
  220.  
  221.   tmp                   = tree->Link[RIGHT];
  222.   newroot               = tmp->Link[LEFT];
  223.   tmp->Link[LEFT]       = newroot->Link[RIGHT];
  224.   newroot->Link[RIGHT]  = tmp;
  225.   tree->Link[RIGHT]     = newroot->Link[LEFT];
  226.   newroot->Link[LEFT]   = tree;
  227.  
  228.   newroot->Link[PARENT] = tree->Link[PARENT];
  229.   newroot->gender       = tree->gender;
  230.   tree->Link[PARENT]    = newroot;
  231.   tree->gender          = LEFT;
  232.   tmp->Link[PARENT]     = newroot;
  233.   tmp->gender           = RIGHT;
  234.  
  235.   if( tree->Link[RIGHT] )
  236.     {
  237.     tree->Link[RIGHT]->Link[PARENT] = tree;
  238.     tree->Link[RIGHT]->gender       = RIGHT;
  239.     }
  240.   if( tmp->Link[LEFT] )
  241.     {
  242.     tmp->Link[LEFT]->Link[PARENT]   = tmp;
  243.     tmp->Link[LEFT]->gender         = LEFT;
  244.     }
  245.   if(newroot->Link[PARENT])
  246.     newroot->Link[PARENT]->Link[newroot->gender] = newroot;
  247.  
  248.   switch( newroot->balance )
  249.     {
  250.     case LEFT :
  251.       tree->balance = EQUAL; tmp->balance = RIGHT; break;
  252.     case EQUAL:
  253.       tree->balance = EQUAL; tmp->balance = EQUAL; break;
  254.     case RIGHT:
  255.       tree->balance = LEFT;  tmp->balance = EQUAL; break;
  256.     }
  257.   newroot->balance = EQUAL;
  258.   return( newroot );
  259.   } /* L2 */
  260.  
  261. static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
  262.   /* ------------------------------------------------------------------------ **
  263.    * Double rotate right.
  264.    *
  265.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  266.    *  Output: A pointer to the new root of the same subtree (now that node
  267.    *          p has been moved).
  268.    * ------------------------------------------------------------------------ **
  269.    */
  270.   {
  271.   ubi_avlNodePtr tmp, newroot;
  272.  
  273.   tmp                   = tree->Link[LEFT];
  274.   newroot               = tmp->Link[RIGHT];
  275.   tmp->Link[RIGHT]      = newroot->Link[LEFT];
  276.   newroot->Link[LEFT]   = tmp;
  277.   tree->Link[LEFT]      = newroot->Link[RIGHT];
  278.   newroot->Link[RIGHT]  = tree;
  279.  
  280.   newroot->Link[PARENT] = tree->Link[PARENT];
  281.   newroot->gender       = tree->gender;
  282.   tree->Link[PARENT]    = newroot;
  283.   tree->gender          = RIGHT;
  284.   tmp->Link[PARENT]     = newroot;
  285.   tmp->gender           = LEFT;
  286.  
  287.   if( tree->Link[LEFT] )
  288.     {
  289.     tree->Link[LEFT]->Link[PARENT]  = tree;
  290.     tree->Link[LEFT]->gender        = LEFT;
  291.     }
  292.   if( tmp->Link[RIGHT] )
  293.     {
  294.     tmp->Link[RIGHT]->Link[PARENT]  = tmp;
  295.     tmp->Link[RIGHT]->gender        = RIGHT;
  296.     }
  297.   if(newroot->Link[PARENT])
  298.     newroot->Link[PARENT]->Link[newroot->gender] = newroot;
  299.  
  300.   switch( newroot->balance )
  301.     {
  302.     case LEFT  :
  303.       tree->balance = RIGHT; tmp->balance = EQUAL; break;
  304.     case EQUAL :
  305.       tree->balance = EQUAL; tmp->balance = EQUAL; break;
  306.     case RIGHT :
  307.       tree->balance = EQUAL; tmp->balance = LEFT;  break;
  308.     }
  309.   newroot->balance = EQUAL;
  310.   return( newroot );
  311.   } /* R2 */
  312.  
  313.  
  314. static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
  315.   /* ------------------------------------------------------------------------ **
  316.    * Adjust the balance value at node *p.  If necessary, rotate the subtree
  317.    * rooted at p.
  318.    *
  319.    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
  320.    *                  subtrees of this node has changed height, so the
  321.    *                  balance value at this node must be adjusted, possibly
  322.    *                  by rotating the tree at this node.
  323.    *          LorR -  Indicates the TALLER subtree.
  324.    *
  325.    *  Output: A pointer to the (possibly new) root node of the subtree.
  326.    *
  327.    *  Notes:  This function may be called after a node has been added *or*
  328.    *          deleted, so LorR indicates the TALLER subtree.
  329.    * ------------------------------------------------------------------------ **
  330.    */
  331.   {
  332.   if( p->balance != LorR )
  333.     p->balance += Normalize(LorR);
  334.   else
  335.     {
  336.     char tallerbal;  /* Balance value of the root of the taller subtree of p. */
  337.  
  338.     tallerbal = p->Link[LorR]->balance;
  339.     if( ( EQUAL == tallerbal ) || ( p->balance == tallerbal ) )
  340.       p = ( (LEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
  341.     else
  342.       p = ( (LEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
  343.     }
  344.   return( p );
  345.   } /* Adjust */
  346.  
  347. static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
  348.                                  ubi_avlNodePtr subtree,
  349.                                  char           LorR )
  350.   /* ------------------------------------------------------------------------ **
  351.    * Rebalance the tree following an insertion.
  352.    *
  353.    *  Input:  Root    - A pointer to the root node of the whole tree.
  354.    *          subtree - A pointer to the node that has just gained a new
  355.    *                    child.
  356.    *          LorR    - Gender of the child that has just been gained.
  357.    *
  358.    *  Output: A pointer to the (possibly new) root of the AVL tree.
  359.    *          Rebalancing the tree moves nodes around a bit, so the node
  360.    *          that *was* the root, may not be the root when we're finished.
  361.    *
  362.    *  Notes:  Rebalance() must walk up the tree from where we are (which is
  363.    *          where the latest change occurred), rebalancing the subtrees
  364.    *          along the way.  The rebalancing operation can stop if the
  365.    *          change at the current subtree root won't affect the rest of
  366.    *          the tree.  In the case of an addition, if a subtree root's
  367.    *          balance becomes EQUAL, then we know that the height of that
  368.    *          subtree has not changed, so we can exit.
  369.    * ------------------------------------------------------------------------ **
  370.    */
  371.   {
  372.   while( subtree )
  373.     {
  374.     subtree = Adjust( subtree, LorR );
  375.     if( PARENT == subtree->gender )
  376.       return( subtree );
  377.     if( EQUAL == subtree->balance )
  378.       return( Root );
  379.     LorR = subtree->gender;
  380.     subtree = subtree->Link[PARENT];
  381.     }
  382.   return( Root );
  383.   } /* Rebalance */
  384.  
  385. static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
  386.                                  ubi_avlNodePtr subtree,
  387.                                  char           LorR )
  388.   /* ------------------------------------------------------------------------ **
  389.    * Rebalance the tree following a deletion.
  390.    *
  391.    *  Input:  Root    - A pointer to the root node of the whole tree.
  392.    *          subtree - A pointer to the node who's child has just "left the
  393.    *                    nest".
  394.    *          LorR    - Gender of the child that left.
  395.    *
  396.    *  Output: A pointer to the (possibly new) root of the AVL tree.
  397.    *          Rebalancing the tree moves nodes around a bit, so the node
  398.    *          that *was* the root, may not be the root when we're finished.
  399.    *
  400.    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
  401.    *          two respects.
  402.    *            * When it calls Adjust(), it passes the *opposite* of LorR.
  403.    *              This is because LorR, as passed into Debalance() indicates
  404.    *              the shorter subtree.  As we move up the tree, LorR is
  405.    *              assigned the gender of the node that we are leaving (i.e.,
  406.    *              the subtree that we just rebalanced).
  407.    *            * We know that a subtree has not changed height if the
  408.    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
  409.    *              what happens in Rebalance().
  410.    * ------------------------------------------------------------------------ **
  411.    */
  412.   {
  413.   while( subtree )
  414.     {
  415.     subtree = Adjust( subtree, RevWay(LorR) );
  416.     if( PARENT == subtree->gender )
  417.       return( subtree );
  418.     if( EQUAL != subtree->balance )
  419.       return( Root );
  420.     LorR = subtree->gender;
  421.     subtree = subtree->Link[PARENT];
  422.     }
  423.   return( Root );
  424.   } /* Debalance */
  425.  
  426.  
  427. /* -------------------------------------------------------------------------- **
  428.  * The next two functions are used for general tree manipulation.  They are
  429.  * each slightly different from their ubi_BinTree counterparts.
  430.  * -------------------------------------------------------------------------- **
  431.  */
  432.  
  433. static void ReplaceNode( ubi_avlNodePtr *parent,
  434.                          ubi_avlNodePtr  oldnode,
  435.                          ubi_avlNodePtr  newnode )
  436.   /* ------------------------------------------------------------------------ **
  437.    * Remove node oldnode from the tree, replacing it with node newnode.
  438.    *
  439.    * Input:
  440.    *  parent   - A pointer to he parent pointer of the node to be
  441.    *             replaced.  <parent> may point to the Link[] field of
  442.    *             a parent node, or it may indicate the root pointer at
  443.    *             the top of the tree.
  444.    *  oldnode  - A pointer to the node that is to be replaced.
  445.    *  newnode  - A pointer to the node that is to be installed in the
  446.    *             place of <*oldnode>.
  447.    *
  448.    * Notes:    Don't forget to free oldnode.
  449.    *           The only difference between this function and the ubi_bt
  450.    *           version is that the node size is sizeof( ubi_avlNode ), not
  451.    *           sizeof( ubi_btNode ).
  452.    * ------------------------------------------------------------------------ **
  453.    */
  454.   {
  455.   register int i;
  456.   register int avlNodeSize = sizeof( ubi_avlNode );
  457.  
  458.   for( i = 0; i < avlNodeSize; i++ )
  459.     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
  460.   (*parent) = newnode;
  461.  
  462.   if(oldnode->Link[LEFT ] )
  463.     (oldnode->Link[LEFT ])->Link[PARENT] = newnode;
  464.   if(oldnode->Link[RIGHT] )
  465.     (oldnode->Link[RIGHT])->Link[PARENT] = newnode;
  466.   } /* ReplaceNode */
  467.  
  468. static void SwapNodes( ubi_btRootPtr  RootPtr,
  469.                        ubi_avlNodePtr Node1,
  470.                        ubi_avlNodePtr Node2 )
  471.   /* ------------------------------------------------------------------------ **
  472.    * This function swaps two nodes in the tree.  Node1 will take the place of
  473.    * Node2, and Node2 will fill in the space left vacant by Node 1.
  474.    *
  475.    * Input:
  476.    *  RootPtr  - pointer to the tree header structure for this tree.
  477.    *  Node1    - \
  478.    *              > These are the two nodes which are to be swapped.
  479.    *  Node2    - /
  480.    *
  481.    * Notes:
  482.    *  This function does a three step swap, using a dummy node as a place
  483.    *  holder.  This function is used by ubi_avlRemove().
  484.    *  The only difference between this function and its ubi_bt counterpart
  485.    *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
  486.    * ------------------------------------------------------------------------ **
  487.    */
  488.   {
  489.   ubi_avlNodePtr *Parent;
  490.   ubi_avlNode     dummy;
  491.   ubi_avlNodePtr  dummy_p = &dummy;
  492.  
  493.   if( Node1->Link[PARENT] )
  494.     Parent = &((Node1->Link[PARENT])->Link[Node1->gender]);
  495.   else
  496.     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
  497.   ReplaceNode( Parent, Node1, dummy_p );
  498.  
  499.   if( Node2->Link[PARENT] )
  500.     Parent = &((Node2->Link[PARENT])->Link[Node2->gender]);
  501.   else
  502.     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
  503.   ReplaceNode( Parent, Node2, Node1 );
  504.  
  505.   if( dummy_p->Link[PARENT] )
  506.     Parent = &((dummy_p->Link[PARENT])->Link[dummy_p->gender]);
  507.   else
  508.     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
  509.   ReplaceNode( Parent, dummy_p, Node2 );
  510.   } /* SwapNodes */
  511.  
  512.  
  513. /* ========================================================================== **
  514.  *         Public, exported (ie. not static-ly declared) functions...
  515.  * -------------------------------------------------------------------------- **
  516.  */
  517.  
  518. ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
  519.   /* ------------------------------------------------------------------------ **
  520.    * Initialize a tree node.
  521.    *
  522.    *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
  523.    *                      initialized.
  524.    *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
  525.    *           same as the input pointer).
  526.    * ------------------------------------------------------------------------ **
  527.    */
  528.   {
  529.   (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
  530.   NodePtr->balance = EQUAL;
  531.   return( NodePtr );
  532.   } /* ubi_avlInitNode */
  533.  
  534. ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
  535.                           ubi_avlNodePtr  NewNode,
  536.                           ubi_btItemPtr   ItemPtr,
  537.                           ubi_avlNodePtr *OldNode )
  538.   /* ------------------------------------------------------------------------ **
  539.    * This function uses a non-recursive algorithm to add a new element to
  540.    * the tree.
  541.    *
  542.    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  543.    *                       the root of the tree to which NewNode is to be added.
  544.    *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
  545.    *                       part of any tree.
  546.    *           ItemPtr  -  A pointer to the sort key that is stored within
  547.    *                       *NewNode.  ItemPtr MUST point to information stored
  548.    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  549.    *                       indicated by ItemPtr is used to place the new node
  550.    *                       into the tree.
  551.    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  552.    *                       the tree, a duplicate node may be found.  If
  553.    *                       duplicates are allowed, then the new node will
  554.    *                       be simply placed into the tree.  If duplicates
  555.    *                       are not allowed, however, then one of two things
  556.    *                       may happen.
  557.    *                       1) if overwritting *is not* allowed, this
  558.    *                          function will return FALSE (indicating that
  559.    *                          the new node could not be inserted), and
  560.    *                          *OldNode will point to the duplicate that is
  561.    *                          still in the tree.
  562.    *                       2) if overwritting *is* allowed, then this
  563.    *                          function will swap **OldNode for *NewNode.
  564.    *                          In this case, *OldNode will point to the node
  565.    *                          that was removed (thus allowing you to free
  566.    *                          the node).
  567.    *                          **  If you are using overwrite mode, ALWAYS  **
  568.    *                          ** check the return value of this parameter! **
  569.    *                 Note: You may pass NULL in this parameter, the
  570.    *                       function knows how to cope.  If you do this,
  571.    *                       however, there will be no way to return a
  572.    *                       pointer to an old (ie. replaced) node (which is
  573.    *                       a problem if you are using overwrite mode).
  574.    *
  575.    *  Output:  a boolean value indicating success or failure.  The function
  576.    *           will return FALSE if the node could not be added to the tree.
  577.    *           Such failure will only occur if duplicates are not allowed,
  578.    *           nodes cannot be overwritten, AND a duplicate key was found
  579.    *           within the tree.
  580.    * ------------------------------------------------------------------------ **
  581.    */
  582.   {
  583.   ubi_avlNodePtr OtherP;
  584.  
  585.   if( !(OldNode) ) OldNode = &OtherP;
  586.   if( ubi_btInsert( RootPtr,
  587.                     (ubi_btNodePtr)NewNode,
  588.                     ItemPtr,
  589.                     (ubi_btNodePtr *)OldNode ) )
  590.     {
  591.     if( (*OldNode) )
  592.       NewNode->balance = (*OldNode)->balance;
  593.     else
  594.       {
  595.       NewNode->balance = EQUAL;
  596.       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
  597.                                                 NewNode->Link[PARENT],
  598.                                                 NewNode->gender );
  599.       }
  600.     return( ubi_trTRUE );
  601.     }
  602.   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
  603.   } /* ubi_avlInsert */
  604.  
  605. ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
  606.                               ubi_avlNodePtr DeadNode )
  607.   /* ------------------------------------------------------------------------ **
  608.    * This function removes the indicated node from the tree, after which the
  609.    * tree is rebalanced.
  610.    *
  611.    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
  612.    *                      the node to be removed.
  613.    *          DeadNode -  A pointer to the node that will be removed.
  614.    *
  615.    *  Output: This function returns a pointer to the node that was removed
  616.    *          from the tree (ie. the same as DeadNode).
  617.    *
  618.    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
  619.    *          strange and evil things will happen to your trees.
  620.    * ------------------------------------------------------------------------ **
  621.    */
  622.   {
  623.   ubi_btNodePtr p,
  624.                *parentp;
  625.  
  626.   /* if the node has both left and right subtrees, then we have to swap
  627.    * it with another node.
  628.    */
  629.   if( (DeadNode->Link[LEFT]) && (DeadNode->Link[RIGHT]) )
  630.     SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) );
  631.  
  632.   /* The parent of the node to be deleted may be another node, or it may be
  633.    * the root of the tree.  Since we're not sure, it's best just to have
  634.    * a pointer to the parent pointer, whatever it is.
  635.    */
  636.   if( DeadNode->Link[PARENT] )
  637.     parentp = (ubi_btNodePtr *)
  638.               &((DeadNode->Link[PARENT])->Link[(DeadNode->gender)]);
  639.   else
  640.     parentp = &( RootPtr->root );
  641.  
  642.   /* Now link the parent to the only grand-child.  Patch up the gender and
  643.    * such, and rebalance.
  644.    */
  645.   if( EQUAL == DeadNode->balance )
  646.     (*parentp) = NULL;
  647.   else
  648.     {
  649.     p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
  650.     p->Link[PARENT]  = (ubi_btNodePtr)DeadNode->Link[PARENT];
  651.     p->gender        = DeadNode->gender;
  652.     (*parentp) = p;
  653.     }
  654.   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
  655.                                             DeadNode->Link[PARENT],
  656.                                             DeadNode->gender );
  657.  
  658.   (RootPtr->count)--;
  659.   return( DeadNode );
  660.   } /* ubi_avlRemove */
  661.  
  662. int ubi_avlModuleID( int size, char *list[] )
  663.   /* ------------------------------------------------------------------------ **
  664.    * Returns a set of strings that identify the module.
  665.    *
  666.    *  Input:  size  - The number of elements in the array <list>.
  667.    *          list  - An array of pointers of type (char *).  This array
  668.    *                  should, initially, be empty.  This function will fill
  669.    *                  in the array with pointers to strings.
  670.    *  Output: The number of elements of <list> that were used.  If this value
  671.    *          is less than <size>, the values of the remaining elements are
  672.    *          not guaranteed.
  673.    *
  674.    *  Notes:  Please keep in mind that the pointers returned indicate strings
  675.    *          stored in static memory.  Don't free() them, don't write over
  676.    *          them, etc.  Just read them.
  677.    * ------------------------------------------------------------------------ **
  678.    */
  679.   {
  680.   if( size > 0 )
  681.     {
  682.     list[0] = ModuleID;
  683.     if( size > 1 )
  684.       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
  685.     return( 1 );
  686.     }
  687.   return( 0 );
  688.   } /* ubi_avlModuleID */
  689.  
  690. /* ============================== The End ============================== */
  691.